Since air pollution has been linked to a plethora of human health problems, strategies to improve air quality are indispensable. Despite the complexity in composition of air pollution, phytoremediation was shown to be effective in cleaning air. Plants are known to scavenge significant amounts of air pollutants on their aboveground plant parts. Leaf fall and runoff lead to transfer of (part of) the adsorbed pollutants to the soil and rhizosphere below. After uptake in the roots and leaves, plants can metabolize, sequestrate and/or excrete air pollutants. In addition, plant-associated microorganisms play an important role by degrading, detoxifying or sequestrating the pollutants and by promoting plant growth. In this review, an overview of the available knowledge about the role and potential of plant–microbe interactions to improve indoor and outdoor air quality is provided. Most importantly, common air pollutants (particulate matter, volatile organic compounds and inorganic air pollutants) and their toxicity are described. For each of these pollutant types, a concise overview of the specific contributions of the plant and its microbiome is presented. To conclude, the state of the art and its related future challenges are presented.